package com.cn.codebrush.数组;

public class No540有序数组中的单一元素 {
    public static void main(String[] args) {

        /**
         * https://blog.csdn.net/qq_45813739/article/details/122934122
         * 当 mid 是偶数时，mid+1=mid⊕1；
         * 当 mid 是奇数时，mid−1=mid⊕1。
         *
         * 例如：
         * 4^1=5
         * 3^1=2
         *
         * 该题用二分查找解决，数组是有序的因此所有相同的元素均相邻，而在要找的单一元素的左边和右边都有偶数个元素且数组的长度为奇数。
         * 采用二分查找，初始左边界是 0，右边界是数组的最大下标。每次取左右边界的平均值 mid 作为待判断的下标，根据 mid 的奇偶性决定和左边或右边的相邻元素比较：
         *
         * 如果 mid 是偶数，则比较nums[mid]和nums[mid+1]是否相等；
         * 如果 mid 是奇数，则比较nums[mid−1]和nums[mid]是否相等。
         *
         * 如果比较结果是相等，则说明要找的单一元素在 mid 的右边，那么调整左边界为 mid+1 ，否则调整右边界为 mid ，一直二分查找直到确定单一元素的位置。
         */


        int[] nums = {1,1,2,3,3,4,4,8,8};
        int[] nums1 =  {3,3,7,7,10,11,11};
        System.out.println(singleNonDuplicate(nums));

    }

    public static int singleNonDuplicate(int[] nums) {
        int left = 0,right = nums.length-1;

        while(left < right){
            int mid = (left+right)/2;
            if(nums[mid] == nums[mid^1]){
                left = mid+1;
            }else {
                right = mid;
            }
        }
        return nums[left];
    }
}
